package Solution101_200.problem105.PreorderandInorder;

import common.TreeNode;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/11 10:14
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,inorder,0,0,inorder.length-1);
    }

    private TreeNode build(int[] pre, int[] in, int preIndex,int inStart,int inEnd){
        if(preIndex>pre.length||inStart>inEnd){
            return null;
        }
        TreeNode node=new TreeNode(pre[preIndex]);
        int nextPre=pre[preIndex];
        int index=-1;
        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==nextPre){
                index=i;
                break;
            }

        }
        if(index==-1){
            return node;
        }
        /*左子树的根结点是下一个值*/
        node.left=build(pre,in,preIndex+1,inStart,index-1);
        /*右子树的根结点*/
        node.right=build(pre,in,preIndex+index-inStart+1,index+1,inEnd);

        return node;
    }

}
